package ysf.com.sort;

import com.alibaba.fastjson.JSON;

/**
 * @author ysf
 * @version 1.0
 * @date 2021/12/11 15:30
 * <p>
 * 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {

        int[] arrys = {2, 10, 5, 9, 1, 6, 7};
        System.out.println(JSON.toJSONString(arrys));
        quickSort(arrys, 0, 6);
        System.out.println(JSON.toJSONString(arrys));
    }

    /**
     * 快速排序
     *
     * @param arrys
     * @param start
     * @param end
     */
    public static void quickSort(int[] arrys, int start, int end) {
        if (start < end) {
            // 把数组中的首位数字作为基准数
            int stard = arrys[start];
            // 记录需要排序的下标
            int low = start;
            int high = end;
            // 循环找到比基准数大的数和比基准数小的数
            while (low < high) {
                // 右边的数字比基准数大
                while (low < high && arrys[high] >= stard) {
                    high--;
                }
                // 使用右边的数替换左边的数
                arrys[low] = arrys[high];
                // 左边的数字比基准数小
                while (low < high && arrys[low] <= stard) {
                    low++;
                }
                // 使用左边的数替换右边的数
                arrys[high] = arrys[low];
            }

            // 把标准值赋给下标重合的位置
            arrys[low] = stard;
            // 处理所有小的数字
            quickSort(arrys, start, low);
            // 处理所有大的数字
            quickSort(arrys, low + 1, end);

        }


    }


}
